#include "BTreeNode.h"
#include <iostream>

using namespace std;

/*
Default BTLeafNode constructor
Main purpose is to set keyCount to 0.
*/
BTLeafNode::BTLeafNode()
{
	//set all chars in the buffer to '0'
	memset(buffer, 0, PageFile::PAGE_SIZE);

	//marks that 
	bool isLeaf = true;
	memcpy(buffer, &isLeaf, sizeof(bool));
	
	//initialize count and PageId
	int initial = 0;
	//the number of Keys is set to 0
	memcpy(buffer+sizeof(bool), &initial, sizeof(int));
	//the default PageId is -2
	initial = -2;
	memcpy(buffer+sizeof(bool)+sizeof(int), &initial, sizeof(PageId));
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::read(PageId pid, const PageFile& pf)
{ 
	//clear out memory in Node
	memset(buffer, 0, PageFile::PAGE_SIZE);
	//read in page file pf to buffer
	if (pf.read(pid, buffer) == 0)
	{
		return 0;
	}
	else
		return RC_FILE_READ_FAILED;
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf)
{
	//write out buffer to PageFile pf
	if (pf.write(pid, buffer) == 0)
	{
		return 0;
	}
	else
		return RC_FILE_WRITE_FAILED;
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount()
{ 
	int keyCount = 0;
	//the number of keys is stored as an integer
		//in 4 bytes of the buffer
	memcpy(&keyCount, buffer+sizeof(bool), sizeof(int));
	return keyCount;
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{ 
	//number of keys in the node
	int keyCount = getKeyCount();

	//the node is full, can't insert
	if(keyCount >= MAX_NUM_LEAF_PAIRS)
	{
		return RC_NODE_FULL;
	}
	
	//increments to traverse buffer
	//where pairs of keys, recordId's begin
	int start = sizeof(int)+sizeof(PageId)+sizeof(bool);
	//size of each pair of key, recordId
	int each = sizeof(int)+sizeof(RecordId);

	//where to begin in the buffer
	char* current = buffer+start;

	//number of keys traversed
		//begins with the first key
	int numKeys = 1;
	//stores value of current key in traversal
	int currentKey = 0;
	//traverse all keys to find where to insert new pair
	while(numKeys <= keyCount)
	{
		//get current key
		memcpy(&currentKey, current, sizeof(int));
		//need to search farther
		if (currentKey < key)
		{
			current += each;
			numKeys++;
		}
		//key < currentKey
		//found location to add new key
		else
		{
			break;
		}
	}

	//to store the back part of the buffer that will be overwritten
		//when the new pair is added
	char backPairs[PageFile::PAGE_SIZE];
	memset(backPairs, 0, PageFile::PAGE_SIZE);
	char * b_ptr = backPairs;

	int backNum = each*(MAX_NUM_LEAF_PAIRS-numKeys+1);
	memcpy(b_ptr, current, backNum*sizeof(char));


	//insert pair to the original buffer
	memcpy(current, &key, sizeof(int));
	memcpy(current+sizeof(int), &rid, sizeof(RecordId));
	current += each;

	//append the rest of the stored pairs into the buffer
		//after the new key
	memcpy(current, b_ptr, backNum-each);

	//update the number of keys in the Node by 1
	keyCount++;
	memcpy(buffer+sizeof(bool), &keyCount, sizeof(int));

	return 0;
}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, int& siblingKey)
{ 
	//increments to traverse the buffer
	int start = sizeof(int)+sizeof(PageId)+sizeof(bool);
	int each = sizeof(int)+sizeof(RecordId);

	//if the number of nodes is odd, the first node gets
		//the extra node
	int keyCount = getKeyCount();
	int secondNode = keyCount/2;
	int firstNode = keyCount-secondNode;

	//check location where the new pair will be inserted
		//(either the original node or the sibling node)
	int check_eid;
	int checkBounds = locate(key, check_eid);
	bool insert_to_one = true;
	if (checkBounds != 0 || check_eid >= firstNode) insert_to_one = false;
	//make sure that the number of keys in the two nodes
		//are either equal or that the original node
		//has one more pair than the sibling
	/*if (firstNode > secondNode && insert_to_one)
	{
		if(check_eid == firstNode)
		{

		}
		else
		{
			secondNode++;
			firstNode--;
		}
	}
	else if (firstNode == secondNode && !insert_to_one)
	{
		secondNode--;
		firstNode++;
	}*/

	//where in buffer to start copying values to the sibling node
	char * backHalf = buffer+start+(each*firstNode);

	//insert the second half of the original node to the sibling node
	for (int i = 0; i < secondNode; i++)
	{
		int curKey = 0;
		RecordId curRecord;
		memcpy(&curKey, backHalf, sizeof(int));
		memcpy(&curRecord, backHalf+sizeof(int), sizeof(RecordId));
			
		int rc = sibling.insert(curKey, curRecord);
		if(rc != 0)
			return rc;
		backHalf += each;
	}

	//update first node's key count
	//the second node's key count will update when keys are inserted
		//with the insert function
	memcpy(buffer+sizeof(bool), &firstNode, sizeof(int));

	//insert in the new pair
	if(insert_to_one)
	{
		int inPair = insert(key, rid);
		if (inPair != 0) return inPair;
	}
	else
	{
		int inPair = sibling.insert(key, rid);
		if (inPair != 0) return inPair;
	}

	
	//set pageid's pointers
		//exchange them
	PageId firstPid = getNextNodePtr();
	PageId secondPid = sibling.getNextNodePtr();
	
	int rc = sibling.setNextNodePtr(firstPid);
	if(rc != 0) return rc;
	rc = setNextNodePtr(secondPid);
	if(rc != 0) return rc; 

	//read the first key from the new sibling node
		//and place its value in siblingkey
	int sibling_key = 0; RecordId sibling_rid;
	rc = sibling.readEntry(0, sibling_key, sibling_rid);
	if(rc != 0) return rc;
	siblingKey = sibling_key;

	return 0;
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{ 
	//to traverse through buffer
	int start = sizeof(int)+sizeof(PageId)+sizeof(bool);
	int each = sizeof(int)+sizeof(RecordId);

	//where pairs begin in buffer
	char * current = buffer+start;

	//number of keys in node
	int keyCount = getKeyCount();
	//i is the location of current key
		//the first key has location 0
		//generally, when n = number of keys
			//the location is n-1
	int i = 0;
	//traverse all the keys
	while(i < keyCount)
	{
		//the current key
		int curKey;
		memcpy(&curKey, current, sizeof(int));
		if(curKey >= searchKey)
		{
			//found a key value larger or equal to searchKey
			eid = i;
			return 0;
		}

		current += each;
		i++;
	}
	//no key value is larger or equal to searchKey
	if(i == keyCount)
	{
		eid = i;
		return RC_NO_SUCH_RECORD;
	}

	return 0;
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{ 
	//to traverse the buffer
	int start = sizeof(int)+sizeof(PageId)+sizeof(bool);
	int each = sizeof(int)+sizeof(RecordId);

	//where pairs of keys begin in buffer
	char * current = buffer+start;

	//number of pairs in buffer
	int keyCount = getKeyCount();

	//eid does not exist in the node
	if(eid >= keyCount)
	{
		return RC_NO_SUCH_RECORD;
	}

	//find location of pair based on the eid
	current += eid*each;

	//set values of the key and recordId from the wanted pair
	memcpy(&key, current, sizeof(int));
	memcpy(&rid, current+sizeof(int), sizeof(RecordId));	

	return 0;
}

/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{ 
	//the pageId in the leaf node that points to the next page
		//is stored in the second four bytes of the buffer
	//return the pageId from the buffer
	PageId myPid;
	memcpy(&myPid, buffer+sizeof(int)+sizeof(bool), sizeof(PageId));

	return myPid;
}

/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{ 
	//store the pid to the buffer
	memcpy(buffer+sizeof(int)+sizeof(bool), &pid, sizeof(PageId));

	return 0;
}






//DONE
BTNonLeafNode::BTNonLeafNode()
{
  memset(buffer, 0, PageFile::PAGE_SIZE);
  	//marks that 
	bool isLeaf = false;
	memcpy(buffer, &isLeaf, sizeof(bool));

	int initial = 0;
	memcpy(buffer+sizeof(bool), &initial, sizeof(int));
}


/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
//DONE
RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{
  memset(buffer, 0, PageFile::PAGE_SIZE);
  return pf.read(pid, buffer);
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
//DONE
RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{
  return pf.write(pid, buffer);
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
//DONE
int BTNonLeafNode::getKeyCount()
{
  //first four bytes store number of records
  int ret = 0;
  memcpy(&ret, buffer+sizeof(bool), sizeof(int));
  return ret; 
}

/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid)
{ 
	
  int pairSize = sizeof(int) + sizeof(PageId);
  int totalSize = (getKeyCount())*pairSize+sizeof(PageId);
  char* buf = buffer+sizeof(int)+sizeof(bool);
  int j = 0;

  //if full, return error.
  if((totalSize + pairSize + sizeof(int)+sizeof(bool)) >= PageFile::PAGE_SIZE)
    return RC_NODE_FULL;
  //create temp page for shifting later
  char* temp = (char*)malloc(PageFile::PAGE_SIZE * sizeof(char));
  
  PageId *curPid = (PageId*)buf;
  buf += sizeof(PageId);
  for(j = 0; j < getKeyCount(); j++)
    {
      int *curKey = (int*)buf;
      if(key < *curKey)
        {
          char* buf2 = buf;
		  size_t size = (getKeyCount()-j)*pairSize;
          memcpy(temp, buf2, size);
		  memcpy(buf2, &key, sizeof(int));
          memcpy(buf2+sizeof(int), &pid, sizeof(PageId));
		  memcpy(buf2+sizeof(PageId)+sizeof(int), temp, size);
          goto end_insert;
        }
      buf+= (sizeof(int) + sizeof(PageId));
    }
  if(j == getKeyCount())
    {
	   memcpy(buf, &key, sizeof(int));
       memcpy(buf+sizeof(int), &pid, sizeof(PageId));
    }

end_insert:
  free(temp);
  int k = getKeyCount();
  k++;
  memcpy(buffer+sizeof(bool), &k, sizeof(int));

  return 0; 
}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{
  if(sibling.getKeyCount() != 0)
    return RC_NO_SUCH_RECORD;
  int pairSize = sizeof(int) + sizeof(PageId);
  int totalSize = getKeyCount()*pairSize+sizeof(PageId);
  char* buf = buffer+sizeof(int)+sizeof(bool);
  int j = 0;

  bool firstHalf = false;
  int keyCount = getKeyCount();
  int firstCount = keyCount/2;
  int secondCount = keyCount - firstCount;
  char* buf2 = buf;

  buf += sizeof(PageId);
  for(j = 0; j < firstCount; j++)
    { 
	  int curKey;
      memcpy(&curKey, buf, sizeof(int));
      if(key < curKey)
      {
          firstHalf = true;
		  break;
      }
      buf += (sizeof(int)+sizeof(PageId));
    }
  if(j >= firstCount)
	  firstHalf = false;

  char* temp = (char*)malloc(PageFile::PAGE_SIZE * sizeof(char));
  memset(temp, 0, PageFile::PAGE_SIZE);
     
  //insert new pair to second half
  if(!firstHalf)
    {
		memcpy(sibling.buffer+sizeof(bool), &secondCount, sizeof(int));
		memcpy(sibling.buffer+sizeof(int)+sizeof(bool), buf2+(firstCount*pairSize), secondCount*pairSize+sizeof(PageId));
		
		sibling.insert(key, pid);
		memcpy(&midKey, sibling.buffer+sizeof(int)+sizeof(bool)+sizeof(PageId), sizeof(int));
		memcpy(sibling.buffer+sizeof(bool), &secondCount, sizeof(int));
		memcpy(buffer+sizeof(bool), &firstCount, sizeof(int));

		memcpy(temp, sibling.buffer+sizeof(int)+sizeof(bool)+pairSize, pairSize*secondCount+sizeof(PageId));
		
		memcpy(sibling.buffer+sizeof(int)+sizeof(bool), temp, pairSize*secondCount+sizeof(PageId));
    }
  else //if(firstHalf)
    {       
		memcpy(temp, buf2+(firstCount*pairSize), secondCount*pairSize+sizeof(PageId));

		memcpy(buffer+sizeof(bool), &firstCount, sizeof(int));
		
		insert(key, pid);

		secondCount--;
		memcpy(sibling.buffer+sizeof(bool), &secondCount, sizeof(int));

		memcpy(&midKey, temp+sizeof(PageId), sizeof(int));
		
		memcpy(sibling.buffer+sizeof(bool)+sizeof(int), temp+sizeof(int)+sizeof(PageId), (secondCount*pairSize)+sizeof(PageId));
	}

  free(temp);

  return 0; 
}


/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{ 
  int numKey = getKeyCount();
  int i;
  char* pidBuf = buffer+sizeof(int)+sizeof(bool);
  PageId curPid;
  char* keyBuf = buffer+sizeof(int)+sizeof(bool)+sizeof(PageId);
  int curKey;
  for(i = 0; i < numKey; i++)
    {
	   memcpy(&curPid, pidBuf, sizeof(PageId));
	   memcpy(&curKey, keyBuf, sizeof(int));

       if(curKey > searchKey)
         {
           pid = curPid;
           return 0;
         }
	   
	   pidBuf += (sizeof(int) + sizeof(PageId));
	   keyBuf += (sizeof(int) + sizeof(PageId));

    }

   memcpy(&curPid, pidBuf, sizeof(PageId));
   pid = curPid; 

  return 0; 
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{ 
  int count = 1;
  memcpy(buffer+sizeof(bool), &count, sizeof(int));
  memcpy(buffer+sizeof(bool)+sizeof(int), &pid1, sizeof(PageId));
  memcpy(buffer+sizeof(bool)+sizeof(int)+sizeof(PageId), &key, sizeof(int));
  memcpy(buffer+sizeof(bool)+sizeof(int)+sizeof(PageId)+sizeof(int), &pid2, sizeof(PageId));
  return 0;
}
